package 贪心;

/**
 * @author TTDB
 * @create 2025/9/23
 */
public class canJump {
     public boolean canJump(int[] nums)
    {
         int n = nums.length;
         boolean[] dp = new boolean[n + 1];
         dp[0] = true;
         for(int i = 1; i < n; i++){
             for(int j = i - 1; j >= 0; j--){
                 if(dp[j] && j + nums[j] >= i)
                     dp[i] = true;
             }
         }
         return dp[n - 1];
    }
    // （贪心的思想）：由每个位置的最远到达位置来推导得到全局的最远到达位置（就是比较最大值就完事了）
    // 具体解法：用一个变量来维护全局可以达到的最远位置，如果下标遍历超过了最远位置，说明有元素不可达；如果全部元素都遍历完了，说明都可以达到
    public boolean canJump2(int[] nums) {
        int farest = 0;
        for(int i=0;i<nums.length;i++){
            //1. 如果超过了最远可达位置，说明不可达
            if(i>farest)
                return false;

            // 2. 说明可达，然后更新边界就完事了
            farest = Math.max(farest,i+nums[i]);
        }
        return true;
    }
}
